package LeetCode;

import java.util.*;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}16:08
 */
public class interview38 {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(permutation("abb")));
    }

    public static String[] permutation(String s) {
        int len = s.length();
        if (len == 0){
            return new String[0];
        }

        char[] arr = s.toCharArray();
        Arrays.sort(arr);

        //由于操作的都是字符串，使用StringBuilder
        StringBuilder builder = new StringBuilder();
        boolean[] used = new boolean[len];

        //为了方便收集结果，使用动态数组
        List<String> res = new ArrayList<>();
        dfs(arr,len,0,used,builder,res);
        return res.toArray(new String[0]);
    }

    /**
     *
     * @param arr   字符数组
     * @param len
     * @param used 当前字符是否使用
     * @param path 从根节点到叶子节点的路径
     * @param res
     * @param depth //当前递归深度
     */
     private static void dfs(char[] arr,int len,int depth,boolean[] used,StringBuilder path,List<String> res){
         if (depth == len){//到底就是成了一组了
             res.add(path.toString());
             return;
         }

         for (int i = 0; i < len; i++){//开始从第一个字符开始整
             if (!used[i]){//意思就是说没有被用过
                 //看看有没有重复的
                 if (i > 0&& arr[i] == arr[i-1] && used[i-1]){
                    continue;
                 }
                 used[i] = true;//表示征用
                 path.append(arr[i]);//确定拼接
                 dfs(arr,len,depth+1,used,path,res);//进行递归

                 //之后进行回滚
                 path.deleteCharAt(path.length()-1);
                 used[i] =false;
             }
         }
     }

//    private static void dfs(char[] arr,int len,int depth,boolean[] used,StringBuilder path,List<String> res){
//        if (depth == len){
//            //path这条路径恰好生成了新的字符对象
//            res.add(path.toString());
//            return;//进行回溯
//        }
//        for (int i = 0; i < len; i++){
//            if (!used[i]){
//                if (i > 0 && arr[i] == arr[i-1] && used[i - 1]){//如果有一样连着的字符的话
//                    continue;
//                }
//                used[i] = true;
//                path.append(arr[i]);//确认后进行拼接
//                dfs(arr,len,depth+1,used,path,res);
//                //递归完成后，需要撤销选择，递归方法执行之前做了什么，递归方法执行以后就需要做相应的逆向操作 也就是往前回滚一手
//                path.deleteCharAt(path.length()-1);//把拼好的回滚一下 回溯法 首先执行这步的一定是最后一次完成后的所以会有一个完整的字符串
//                used[i] = false;
//            }
//        }
//    }
}
